package leetcode

// Definition for a binary tree node.
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

// https://leetcode.com/problems/diameter-of-binary-tree/
func DiameterOfBinaryTree(root *TreeNode) int {
	var max int = 0
	traversal(root, &max)
	return max
}

func traversal(root *TreeNode, max *int) int {
	if root == nil {
		return 0
	}
	left := traversal(root.Left, max)
	right := traversal(root.Right, max)
	if left+right > *max {
		*max = left + right
	}
	if left > right {
		return left + 1
	}
	return right + 1
}
